package com.nine.algorithm.recursion.bubblesort;

import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertArrayEquals;

/**
 * @author nine
 * @version 1.0
 * @description 递归冒泡排序
 * 将数组划分为两个部分 [0...j] 和 [j+1...n-1]
 * 左边的元素已经排序，右边的是未排序的
 * 每次遍历，找到未排序部分的最大元素，放到已排序部分的末尾
 * @date 24/4/30 22:49
 */
public class BubbleSort {

	@Test
	@DisplayName("测试冒泡排序递归实现")
	public void testBubbleSort() {
		int[] a = {1, 5, 3, 7, 9, 4, 6, 2};
		int[] expected = {1, 2, 3, 4, 5, 6, 7, 9};
		sort(a);
		assertArrayEquals(expected, a);
	}

	public static void sort(int[] a) {
		bubble2(a, a.length - 1);
	}

	// j：未排序区域的右边界
	private static void bubble(int[] a, int j) {
		if (j < 1) {
			return;
		}
		for (int i = 0; i < j; i++) {
			if (a[i] > a[i + 1]) {
				int t = a[i];
				a[i] = a[i + 1];
				a[i + 1] = t;
			}
		}
		bubble(a, j - 1);
	}

	// 优化冒泡排序
	private static void bubble2(int[] a, int j) {
		if (j < 1) {
			return;
		}
		// 添加变量x，初始值在0，每发生一次交换，将i的值给x，意味着当前交换的最小值的位置，保证x比后面的元素都小
		// 如果后面没有发生交换，则说明后面的元素已经有序，那么递归就是用x就行
		int x = 0;
		for (int i = 0; i < j; i++) {
			if (a[i] > a[i + 1]) {
				int t = a[i];
				a[i] = a[i + 1];
				a[i + 1] = t;
				x = i;
			}
		}
		bubble(a, x);
	}
}
